import sys
def min_max_difference(weights, k):
    n = len(weights) #珠子的数量
    # 如果珠子数量少于背包数量，则无法分配
    if n<k:
        return 0
    # 创建(n+1)*(k+1)的二维数组dp_min和dp_max，初始化为正无穷和负无穷
    dp_min = [[sys.maxsize] * (k + 1) for _ in range(n + 1)]
    dp_max = [[-sys.maxsize] * (k + 1) for _ in range(n + 1)]

    # 没有珠子的时候，分成 0 个背包，价值为0。
    dp_min[0][0] = 0
    dp_max[0][0] = 0

    # 前缀和数组，用于快速计算子数组的和
    #在计算前缀和时，需要一个额外的空间来存储前 0 个元素的和（即 0），这使得索引的使用更加方便，所以开辟n+1个空间
    prefix_sum = [0] * (n + 1)
    #这里 i 的循环从 1 开始，到 n + 1 结束，这样我们可以确保 prefix_sum 的第 i 个位置存储了 weights 数组前 i 个元素的总和。
    for i in range(1, n + 1):
        prefix_sum[i] = prefix_sum[i - 1] + weights[i - 1]

    # 动态规划过程
    for i in range(1, n + 1):  #珠子数
        for j in range(1, k + 1):  # 对于每个 i，将这 i 个珠子分成 j 个背包，j 最多为 k（最大背包数）。
            for l in range(j - 1, i):
                price = weights[l] + weights[i - 1]
                if dp_min[l][j - 1] != sys.maxsize:  # 要确保dp_min[l][j - 1]有效
                    dp_min[i][j] = min(dp_min[i][j], dp_min[l][j - 1] + price)
                if dp_max[l][j - 1] != -sys.maxsize:  # 确保dp_max[l][j - 1]有效
                    dp_max[i][j] = max(dp_max[i][j], dp_max[l][j - 1] + price)

    # 返回最大的差距
    return dp_max[n][k] - dp_min[n][k]



weights = [1,3,5,1]
k = 2
print(min_max_difference(weights, k))
